//自己的版本
public class code2 {
    //在上题的基础上增加了首尾相连
    public int rob(int[] nums) {
        //分类拆分成已知问题
        int n = nums.length;
        if(n==1) return nums[0];//处理特殊情况
        return Math.max(rob1(nums,0,n-2),rob1(nums,1,n-1));//前面不写成rob1(0,n-2)可以避免【1，2】这样的nums情况
    }
    public int rob1(int[] nums,int left,int right) {
        if(left>right) return 0;
        int n = nums.length;

        int[] f = new int[n];
        int[] g = new int[n];

        f[left] = nums[left];//注意这里不是f[0] = nums[0],因为初始位置不一样

        for(int i=left+1;i<=right;i++) {
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }

        return Math.max(f[right],g[right]);
    }
}
